package calculate24.play.common.calculate24;

import java.util.ArrayList;

//输入4个数，输出能算出24点的所有可能的解
public class Calculate24 {
    public ArrayList<String> resultSet;

    public Calculate24(int[] numbers) {
        ArrayList<OperationTree> operators = new ArrayList<OperationTree>();
        for(int number: numbers) {
            operators.add(new OperationTree(number));
        }
        resultSet = new ArrayList<String>();
        recur(operators);
        ArrayList<String> oldResultSet = resultSet;
        resultSet = new ArrayList<String>();
        for(String str: oldResultSet) {
            if(!resultSet.contains(str)) {
                resultSet.add(str);
            }
        }
    }

    //递归：4个数运算一次剩下3个数，3个数运算一次剩下2个数，2个数运算剩下1个数，若这1个数等于24，则为可行解
    private void recur(ArrayList<OperationTree> operators) {
        if(operators.size() == 1) {
            if(operators.get(0).value == 24) {
                resultSet.add(operators.get(0).toString());
            }
            return;
        }
        //穷举：每两个操作数两两做加减乘除四种运算
        for(int i = 0; i < operators.size(); ++i) {
            for(int j = 0; j < operators.size(); ++j) {
                if(i != j) {
                    OperationTree left;
                    OperationTree right;
                    if(i < j) {
                        // i < j时，若先移除元素i，则后面的元素会前移一位
                        right = operators.remove(j);
                        left = operators. remove(i);
                    } else {
                        left = operators. remove(i);
                        right = operators.remove(j);
                    }
                    final char[] OPERATIONS = {'+', '-', '*', '/'};
                    for(char operation: OPERATIONS) {
                        if(operation == '-'
                                || operation == '/' && right.value != 0 && left.value % right.value == 0
                                || operation == '+' && i < j //加法乘法有交换律，因此对称的解只需保留一个
                                || operation == '*' && i < j) {
                            operators.add(new OperationTree(operation, left, right));
                            recur(operators);
                            operators.remove(operators.size()-1);
                        }
                    }
                    if(i < j) {
                        operators.add(i, left);
                        operators.add(j, right);
                    } else {
                        operators.add(j, right);
                        operators.add(i, left);
                    }
                }
            }
        }
    }

}

